{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "2b5644b8",
   "metadata": {},
   "source": [
    "# 二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1aa92f16",
   "metadata": {},
   "source": [
    "二叉树由两个对象组成，一个是节点对象，一个是树对象"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "19b0378e",
   "metadata": {},
   "source": [
    "Q：寻找二叉树所有叶节点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "b396a483",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    \"\"\"节点类\"\"\"\n",
    "    def __init__(self, val=-1, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "\n",
    "class Tree:\n",
    "    \"\"\"树类\"\"\"\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "        self.queue = [] #使用列表模拟队列\n",
    "        \n",
    "    def add(self, val):\n",
    "        \"\"\"添加节点\"\"\"\n",
    "        node = Node(val) # 初始化一个空节点 ？\n",
    "        \n",
    "        if self.root.val == -1: # 如果树是空的，则对根节点赋值\n",
    "            self.root = node\n",
    "            self.queue.append(self.root)\n",
    "        else:\n",
    "            treeNode = self.queue[0] # 此结点的子树还没有齐。\n",
    "            if treeNode.left is None:\n",
    "                treeNode.left = node # 左子树变成节点（初始此节点左右都是None）\n",
    "                self.queue.append(treeNode.left)\n",
    "            else:\n",
    "                treeNode.right = node\n",
    "                self.queue.append(treeNode.right)\n",
    "                self.queue.pop(0) # 如果该结点存在右子树，将此结点丢弃。\n",
    "\n",
    "    # 根节点和叶子结点递归调用计算每个节点的左右子节点个数\n",
    "    def leave(self,root):\n",
    "        if root is None:\n",
    "            return 0\n",
    "        elif root.left is None and root.right is None :\n",
    "            return 1\n",
    "        else:\n",
    "            return (self.leave(root.left)+self.leave(root.right))   # 递归遍历所有左子树右子树，当左右都为None时才算1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "c5a37717",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "叶子节点个数: 5\n"
     ]
    }
   ],
   "source": [
    "\"\"\"主函数\"\"\"\n",
    "vals = range(10)           #生成十个数据作为树节点\n",
    "tree = Tree()          #新建一个树对象\n",
    "for val in vals:\n",
    "    tree.add(val)           #逐个添加树的节点\n",
    "\n",
    "print ('叶子节点个数:', tree.leave(tree.root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6d3ba780",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f291ad32",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
